package ltaa.sponsoredsearch.GAM;

import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Arrays;

class BipartiteGraph {
	private Map<Integer, Set<Integer>> bidderToCopies;
	private Map<Integer, Bidder> copyToBidder;
	private int numOfBidderCopies;
	private int numOfAvailItems;
	private Map<Integer,Double> bidderUtilities;
	private Map<Integer,Double> itemPrices;
	private Set<Edge> edges;

	private Map<Integer, Integer> currentMatch;
	private Map<Integer, Integer> reverseMatch;


	private Map<Integer, Path> toBidders;
	private Map<Integer, Path> toItems;

	public BipartiteGraph(Bidder[] bidders, int totItems) {
		bidderToCopies = new HashMap<Integer, Set<Integer>>();
		copyToBidder = new HashMap<Integer, Bidder>();
		numOfBidderCopies = 0;
		numOfAvailItems = totItems;
		bidderUtilities = new HashMap<Integer,Double>();
		itemPrices = new HashMap<Integer,Double>();
		edges = new HashSet<Edge>();

		Bidder bidder;
		Integer newBidder;
		Integer newCopy;
		Set<Integer> copies;
		for (int i = 0; i < bidders.length; i++) {
			bidder = bidders[i];
			
			newBidder = new Integer(i);
			copies = new HashSet<Integer>();
			for (int j = 0; j < bidder.getNumItems(); j++) {
				newCopy = new Integer(numOfBidderCopies++);
				copies.add(newCopy);
				bidderUtilities.put(newCopy, new Double(GeneralizedAuctionMechanism.MAX_VALUE));
				copyToBidder.put(newCopy, bidder);
			}

			bidderToCopies.put(newBidder, copies);
		}

		for (int i = 0; i < totItems; i++) {
			itemPrices.put(new Integer(i), new Double(0.0));
		}

		currentMatch = new HashMap<Integer,Integer>();
		reverseMatch = new HashMap<Integer,Integer>();


		if (!verbose()) {
			printStatus();
		}
	}

	private void printStatus() {
			System.out.println("****************************************");
			System.out.println("bidderToCopies:" + bidderToCopies.toString());
			System.out.println("copyToBidder:" + copyToBidder.toString());
			System.out.println("bidderUtilities:" + bidderUtilities.toString());
			System.out.println("itemPrices:" + itemPrices.toString());
			System.out.println("currentMatch:" + currentMatch.toString());
			System.out.println("----------------------------------------");
	}

	public Outcome solve() {
		Integer i0 = new Integer(0);
		while (true) {
			if (currentMatch.keySet().containsAll(bidderUtilities.keySet())) {
				break;
			}


			while (currentMatch.containsKey(i0)) {
				i0 = new Integer(i0.intValue() + 1);
				if (i0.intValue() >= numOfBidderCopies) {
					i0 = new Integer(0);
				}
			}
			
			if (verbose()) {
				printStatus();
			}
			String[] lastEdge = {""};
			Double[] wP = {0.0};
			if (chatty()) {
				System.out.println("Attempting to find an augmenting path from: "+i0);
			}
			Integer[] path = findAugmentingPath(i0, lastEdge, wP);

			if (path.length < 1) {
				break;
			}

			if (verbose()) {
				System.out.print("Found the following augmenting path: ");
				System.out.print(Arrays.toString(path));
				System.out.println(", which has weight w(P)="+wP[0]);
			}

			//We will need the reserve price at which i_l can be matched to j_{l+1}
			double reservePriceForLastEdge = (new Edge(path[path.length-2],
			path[path.length-1])).reserve();

			//TODO: that's really ugly, gonna have to change it.
			// ----- Ok, may be not that ugly now, used to be bad ;)
			Map<Integer,Double> newBidUtilities = new HashMap<Integer, Double>();
			Map<Integer,Double> newItemPrices = new HashMap<Integer, Double>();

			// Update the utilities.
			Iterator bidders = bidderUtilities.keySet().iterator();
			while (bidders.hasNext()) {
				Integer bidder = (Integer) bidders.next();
				Double oldUtility = bidderUtilities.get(bidder);
				double distance = GeneralizedAuctionMechanism.MAX_VALUE;
				if (toBidders.containsKey(bidder)) {
					distance = toBidders.get(bidder).getWeight();
				}
				double newUtility = oldUtility.doubleValue() - Math.max(wP[0] -
				distance, 0);

				if (chatty()) {
					System.out.print("\tUpdated bidder's "+bidder.intValue());
					System.out.print(" utility. ");
					System.out.println("(was "+oldUtility+" is "+newUtility+")");
				}

				newBidUtilities.put(bidder, new Double(newUtility));
			}

			// Update the prices.
			Iterator items = itemPrices.keySet().iterator();
			while (items.hasNext()) {
				Integer item = (Integer) items.next();
				Double oldPrice = itemPrices.get(item);
				double distance = GeneralizedAuctionMechanism.MAX_VALUE;
				if (toItems.containsKey(item)) {
					distance = toItems.get(item).getWeight();
				}
				
				if (extreme()) {
					System.out.println("\tFB Path cost from bidder "+i0+" to item "+
					item+": "+distance);
				}
				double newPrice = oldPrice.doubleValue() + Math.max(wP[0] -
				distance, 0);
				if (lastEdge[0].equals("Reserve")) {
					newPrice = Math.max(newPrice, reservePriceForLastEdge);
				}

				if (chatty()) {
					System.out.print("\tUpdated item's "+item.intValue());
					System.out.print(" price. ");
					System.out.println("(was "+oldPrice+" is "+newPrice+")");
				}

				newItemPrices.put(item, new Double(newPrice));
			}

			//TODO: end of the (after all) not so ugly trick.
			bidderUtilities = newBidUtilities;
			itemPrices = newItemPrices;

			// Update the matching.
			if (lastEdge[0].equals("Terminal")) {
				// Case 1.
				if (extreme()) {
					System.out.print("\tApplying maching update rule 1: ");
					System.out.println("Terminal");
				}
				matchPath(path);
			} else if (lastEdge[0].equals("Max")) {
				//Case 2.
				if (path[path.length - 2].equals(path[path.length -1])) {
					//Case 2.a, max price reached on a matching edge.
					//Flip all matching / non-matching edges along P.
				if (extreme()) {
					System.out.print("\tApplying maching update rule 2.a: ");
					System.out.println("Max - matching edge");
				}
					matchPath(path);
				} else {
				if (extreme()) {
					System.out.print("\tApplying maching update rule 2.b: ");
					System.out.println("Max - non-matching edge");
				}
					//Case 2.b, max price reached on a non-matching edge.
					// do nothing ;)
				}
			} else if (lastEdge[0].equals("Reserve")){
				//Case 3. (the complex one...)
				if (!reverseMatch.containsKey(path[path.length-1])) {
					//Case 3.a, the last item in the path was unmatched.
					//This increases the size of the matching.
					if (extreme()) {
						System.out.print("\tApplying maching update rule 3.a: ");
						System.out.println("Reserve - non-matching edge");
					}
					matchPath(path);
				} else if (reservePriceForLastEdge <=
				itemPrices.get(path[path.length-1])) {
					//Case 3.b, reserve price isn't high enough for attibution
					//Do nothing.
					if (extreme()) {
						System.out.print("\tApplying maching update rule 3.b: ");
						System.out.println("Reserve - lower than current");
					}
				} else {
					//Case 3.c, if P is indeed a path (i.e. there is no node visited
					//twice), then we remove (i_{l+1}, j_{l+1}) from the matching and flip
					//matching and non-matching edges along P. (the size of the matching
					//doesn't change.
					if (extreme()) {
						System.out.print("\tApplying maching update rule 3.c: ");
						System.out.println("Reserve - higher than current");
					}
					int cycleIndex = cycleAt(path);
					if (cycleIndex == path.length) {
						Integer il1 = reverseMatch.get(path[path.length-1]);
						currentMatch.remove(il1);
						matchPath(path);
					}
					//If P isn't a path, then the end of the augmenting path from a cycle.
					else {
						Integer[] cycle = new Integer[path.length-cycleIndex];
						System.arraycopy(path, cycleIndex-1, cycle, 0, cycle.length);
						matchPath(cycle);
					}
				}
			}
		}

		if (verbose()) {
			printStatus();
		}

		Outcome myOutcome = new Outcome();


		Iterator bidders = bidderUtilities.keySet().iterator();
		while (bidders.hasNext()) {
			Integer bidderCopy = (Integer) bidders.next();
			Bidder bidder = copyToBidder.get(bidderCopy);
			Set<Integer> myItems;
			double myPayment;
			if (myOutcome.attribution.containsKey(bidder)) {
				myItems = myOutcome.attribution.get(bidder);
			} else {
				myItems = new HashSet<Integer>();
			}
			if (myOutcome.payments.containsKey(bidder)) {
				myPayment = myOutcome.payments.get(bidder);
			} else {
				myPayment = 0.0;
			}
			if (currentMatch.containsKey(bidderCopy)) {
				Integer myAttributedItem = currentMatch.get(bidderCopy);
				myItems.add(myAttributedItem);
				myPayment += itemPrices.get(myAttributedItem).doubleValue();
			}
			myOutcome.attribution.put(bidder, myItems);
			myOutcome.payments.put(bidder, new Double(myPayment));
		}

		return myOutcome;
	}

	private int cycleAt(Integer[] path) {
		for (int i = 0; i < path.length-1; i++) {
			if (path[i].equals(path[path.length-1])) {
				return i;
			}
		}
		return path.length;
	}

	private void matchPath(Integer[] path) {
		int i = 0;
		while (i < (path.length-1)) {
			Integer bidder = new Integer(path[i++]);
			Integer item = new Integer(path[i++]);
			reverseMatch.remove(currentMatch.get(bidder));
			currentMatch.remove(reverseMatch.get(item));
			if (item.intValue() < numOfAvailItems) {
				if (extreme()) {
					System.out.println("\t\tMatching bidder "+bidder+
					" with item "+item);
				}
				currentMatch.put(bidder, item);
				reverseMatch.put(item, bidder);
			} else {
				if (extreme()) {
					System.out.println("\t\tUnmatching bidder "+bidder);
				}
				currentMatch.remove(bidder);
			}
		}
	}

	private Integer[] findAugmentingPath(Integer source, String[] lastEdge,
	Double[] weight) {
		Iterator it = bidderUtilities.keySet().iterator();

		double best = GeneralizedAuctionMechanism.MAX_VALUE;
		Integer[] curBest = {};

		getShortestFBPaths(source);

		Integer ik;
/*		Integer[] minFBPath;
		double[] cur_weight = {GeneralizedAuctionMechanism.MAX_VALUE};
		*/
		double[] last_weight = {0.0};
		
		while (it.hasNext()) {
			ik = (Integer) it.next();
			
			if (extreme()) {
				System.out.println("\tTrying to get a forw-back path from "+source+" to "+ik);
			}
			//Set<Integer> visited = new HashSet<Integer>();
			if (!toBidders.containsKey(ik)) {
				if (extreme()) {
					System.out.println("Skipping "+ik);
				}
				continue;
			}

			Path minFBPath = toBidders.get(ik);
	
			if (extreme()) {
				System.out.println("\tBest found was "
				+Arrays.toString(minFBPath.getPath()));
			}

			
			if (extreme()) {
				System.out.println("\tChecking for a end edge from "+ik);
			}
			Integer endNode = minPriceEndEdge(ik,last_weight, lastEdge);
			if (extreme()) {
				System.out.println("\tBest found was edge to item "+endNode+", at cost " +
				last_weight[0]);
			}

			if ( (minFBPath.getWeight() + last_weight[0]) < best) {
				best = minFBPath.getWeight() + last_weight[0];

				curBest = append(endNode, minFBPath.getPath()); 
			}
		}

		weight[0] = best;

		if (chatty()) {
			System.out.println("best path found is: "+Arrays.toString(curBest)+", which has weight "+best);
		}

		return curBest;
	}


	private Integer[] append(Integer ik, Integer[] cur) {
		Integer[] res = new Integer[cur.length + 1];
		for (int i = 0; i < cur.length; i++) {
			res[i] = cur[i];
		}
		res[cur.length] = ik;

		return res;
	}

	private class Path {
		private double weight;
		private Integer[] path;

		public Path() {
			weight = GeneralizedAuctionMechanism.MAX_VALUE;
			path = new Integer[0];
		}

		public void setValues(double w, Integer[] p) {
			weight = w;
			path = p;
		}

		public double getWeight() {
			return weight;
		}

		public Integer[] getPath() {
			return path;
		}

		public String toString() {
			return "(<"+weight+">, "+Arrays.toString(path)+")";
		}
	}

	private void getShortestFBPaths(Integer from) {
		toItems = new HashMap<Integer, Path>();
		toBidders = new HashMap<Integer, Path>();

		Iterator it = itemPrices.keySet().iterator();
		//Start by stating that the path to oneself is of length 0.
		Path toSelf = new Path();
		Integer[] pathToSelf = {from};
		toSelf.setValues(0.0, pathToSelf);
		toBidders.put(from, toSelf);

		
		if (extreme()) {
			System.out.println("\t-+-+-+-+-");
		}

		//compute first order reachability
		while (it.hasNext()) {
			Integer item = (Integer) it.next();
			Edge myEdge = new Edge(from, item);
			double forward = myEdge.getForward();
			if (forward < GeneralizedAuctionMechanism.MAX_VALUE) {
				if (extreme()) {
					System.out.println("\tEdge "+myEdge+
					" has a forward weight of	"+forward);
				}
				Path f = new Path();
				Integer[] p = {from, item};
				f.setValues(forward, p);
				toItems.put(item, f);
			}
		}

		int i = 0;
		while (i <= currentMatch.size()) {
			//From the reachable items, which bidders can we reach back?
			Iterator items1 = toItems.keySet().iterator();

			while (items1.hasNext()) {
				Integer item = (Integer) items1.next();

				Iterator bidders = bidderUtilities.keySet().iterator();

				while (bidders.hasNext()) {
					Integer bidder = (Integer) bidders.next();

					Edge testEdge = new Edge(bidder, item);

					double back = testEdge.getBackward();
					double prefixW = toItems.get(item).getWeight();
					Integer[] prefix = toItems.get(item).getPath();
					
					if (extreme()) {
						System.out.println("\tEdge "+testEdge+
						" has a backard weight of "+back);
					}

					if (back < GeneralizedAuctionMechanism.MAX_VALUE) {
						if (toBidders.containsKey(bidder)) {
							double oldW = toBidders.get(bidder).getWeight();

							if (prefixW + back < oldW) {
								toBidders.get(bidder).setValues(prefixW + back,
								append(bidder,prefix));
								if (extreme()) {
									System.out.println("\t\tUpdated path: "+toBidders.get(bidder));
								}
							}
						} else {
							if (prefixW + back < GeneralizedAuctionMechanism.MAX_VALUE) {
								Path toBidder = new Path();
								toBidder.setValues(prefixW + back, append(bidder,
								prefix));
								if (extreme()) {
									System.out.println("\t\tNew path: "+toBidders.get(bidder));
								}
								toBidders.put(bidder, toBidder);

							}
						}
					}
				}
			}
			
			//From already existing and newly added bidders, what items can we reach?
			Iterator bidders = toBidders.keySet().iterator();

			while (bidders.hasNext()) {
				Integer bidder = (Integer) bidders.next();

				Iterator items = itemPrices.keySet().iterator();

				while (items.hasNext()) {
					Integer item = (Integer) items.next();

					Edge testEdge = new Edge(bidder, item);

					double forward = testEdge.getForward();
					double prefixW = toBidders.get(bidder).getWeight();
					Integer[] prefix = toBidders.get(bidder).getPath();
					if (extreme()) {
						System.out.println("\tEdge "+testEdge+
						" has a forward weight of "+forward);
					}

					if (forward < GeneralizedAuctionMechanism.MAX_VALUE) {
						if (toItems.containsKey(item)) {
							double oldW = toItems.get(item).getWeight();

							if (prefixW + forward < oldW) {
								toItems.get(item).setValues(prefixW + forward, append(item, prefix));
								if (extreme()) {
									System.out.println("\t\tUpdated path: "+toItems.get(item));
								}
							}
						} else {
							if (prefixW + forward < GeneralizedAuctionMechanism.MAX_VALUE) {
								Path toItem = new Path();
								toItem.setValues(prefixW + forward, append(item, prefix));
								toItems.put(item, toItem);
								if (extreme()) {
									System.out.println("\t\tUpdated path: "+toItems.get(item));
								}
							}
						}
					}
				}
			}
			
			if (extreme()) {
				System.out.println("\tAt iteration "+i+", we have:");
				System.out.println("\tTo bidders:");
				System.out.println("\t\t"+toBidders.toString());
				System.out.println("\tTo Items");
				System.out.println("\t\t"+toItems.toString());
			}

			i++;
		}
	}

	private Integer minPriceEndEdge(Integer i0, double[] weight, String[] lastEdge) {
		Integer me = null;
		double minPrice = GeneralizedAuctionMechanism.MAX_VALUE;

		Iterator it = itemPrices.keySet().iterator();

		Integer item;
		while (it.hasNext()) {
			item = (Integer) it.next();
			Edge myEdge = new Edge(i0, item);
			if (extreme()) {
				System.out.println("\tChecking Edge : " + myEdge.toString());
			}
			if (myEdge.getReserve() < minPrice) {
				minPrice = myEdge.getReserve();
				me = item;
				lastEdge[0] = "Reserve";
			}
			if (myEdge.getMax() < minPrice) {
				minPrice = myEdge.getMax();
				me = item;
				lastEdge[0] = "Min";
			}
			if (myEdge.getTerminal() < minPrice) {
				minPrice = myEdge.getTerminal();
				me = item;
				lastEdge[0] = "Terminal";
			}
		}

		weight[0] = minPrice;
		return me;
	}


	private class Edge {
		Integer bidder;
		Integer item;

		public Edge(Integer a, Integer b) {
			this.bidder = a;
			this.item = b;
		}

		public boolean equals(Edge that) {
			return (this.bidder == that.getBidder() && this.item == that.getItem());
		}

		public Integer getBidder() {
			return this.bidder;
		}

		public Integer getItem() {
			return this.item;
		}

		public double getForward() {
			if (!anotherMe() && reserve() <= price() && price() < max()) {
				return (utility() + price() - valuation());
			} else {
				return GeneralizedAuctionMechanism.MAX_VALUE;
			}
		}

		public double getBackward() {
			if (this.item.intValue() < numOfAvailItems && currentMatch.containsKey(this.bidder) && currentMatch.get(this.bidder).equals(this.item)) {
				return (valuation() - utility() - price());
			} else {
				return GeneralizedAuctionMechanism.MAX_VALUE;
			}
		}

		public double getReserve() {
			if ( !anotherMe() && (utility() + reserve()) > valuation() && max() > reserve()) {
				return (utility() + reserve() - valuation());
			} else {
				return GeneralizedAuctionMechanism.MAX_VALUE;
			}
		}
		
		public double getMax() {
			if (!anotherMe() && (utility() + max()) > valuation() && max() > reserve()) {
				return (utility() + max() - valuation());
			} else {
				return GeneralizedAuctionMechanism.MAX_VALUE;
			}
		}

		public double getTerminal() {
			if (this.item.intValue() >= numOfAvailItems && utility() > 0) {
				return utility();
			} else {
				return GeneralizedAuctionMechanism.MAX_VALUE;
			}
		}

		private double utility() {
			return bidderUtilities.get(this.bidder).doubleValue();
		}

		private double price() {
			return itemPrices.get(this.item).doubleValue();
		}

		private double valuation() {
			int plouf = this.item.intValue();
			if (plouf < numOfAvailItems) {
				double val = copyToBidder.get(bidder).bid(plouf);
				return val;
			} else {
				return 0.0;
			}
		}

		public double reserve() {
			return 0.0;
		}

		private double max() {
			return valuation();
		}
		
		public String toString() {
			return "("+bidder+", "+item+")";
		}
		
		//Is the item matched to another copy of the bidder?
		private boolean anotherMe() {
			if (reverseMatch.containsKey(item)) {
				Integer matchedTo = reverseMatch.get(item);
				Bidder myRealBidder = copyToBidder.get(bidder);
				Bidder thineRealBidder = copyToBidder.get(matchedTo);
				return myRealBidder == thineRealBidder;
			}

			return false;
		}

	}

	private boolean verbose() {
		return GeneralizedAuctionMechanism.verbosity >= GeneralizedAuctionMechanism.VERBOSE;
	}

	private boolean chatty() {
		return GeneralizedAuctionMechanism.verbosity >= GeneralizedAuctionMechanism.CHATTY;
	}

	private boolean extreme() {
		return GeneralizedAuctionMechanism.verbosity >= GeneralizedAuctionMechanism.EXTREME;
	}
}
